令
不难发现质数有以下取值:
所以可以得到:
整除分块即可。
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN = 4e6 , Mod = 998244353;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , Sumf[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) { prime[ ++ prnum ] = i; mu[ i ] = -1; }
for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) break;
mu[ i * prime[ j ] ] = -mu[ i ];
}
}
for( int i = 1 ; i <= MAXN ; i ++ ) Sumf[ i ] = Sumf[ i - 1 ] + mu[ i ];
}
int SumF( LL l , LL r ) {
return ( Sumf[ (int)sqrt( r ) ] - Sumf[ (int)sqrt( l - 1 ) ] + Mod ) % Mod;
}
int Solve( LL n , LL m ) {
int Ans = 0;
for( LL l = 1 , r ; l <= min( n , m ) ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans = Add( Ans , Mul( Mul( n / l % Mod , m / l % Mod ) , SumF( l , r ) ) );
}
return Ans;
}
LL n , m;
int main( ) {
sieve();
scanf("%lld %lld",&n,&m);
printf("%d\n", Solve( n , m ) );
return 0;
}